package 数据结构和算法.剑指offer.栈和队列.最小栈;

import java.util.Stack;

/**
 * 最小栈
 * <p>
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 * <p>
 * push(x) —— 将元素 x 推入栈中。
 * pop() ——  删除栈顶的元素。
 * top() —— 获取栈顶元素。
 * min() —— 检索栈中的最小元素。
 * <p>
 * 使用两个辅助栈，一个用于存放当前输入的数据，
 * 另一个用于维护最小值。对于存放最小值的栈helper，
 * 如果栈为空或者栈顶的元素大于当前要放入data中的元素，那么helper栈执行入栈操作。
 */
public class Test {
    private Stack<Integer> data;
    private Stack<Integer> helper;

    public Test() {
        data = new Stack<>();
        helper = new Stack<>();
    }

    public void push(int x) {
        data.add(x);
        if (helper.isEmpty() || helper.peek() >= x) {
            helper.add(x);
        } else {
            helper.add(helper.peek());
        }
    }

    public void pop() {
        if (!data.isEmpty()) {
            helper.pop();
            data.pop();
        }
    }

    public int top() {
        if (!data.isEmpty()) {
            return data.peek();
        }
        throw new RuntimeException("栈中元素为空，此操作非法");
    }

    public int min() {
        if (!helper.isEmpty()) {
            return helper.peek();
        }
        throw new RuntimeException("栈中元素为空，此操作非法");
    }
}
